/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 递归的结束条件：
        // 1.当节点为空时说明到了最底下的节点
        // 2.当root为q或者p时返回
        if (root == nullptr || root == q || root == p) {
            return root;
        }
        // 递归判断此节点的左右子树是否包含p，q节点
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // 如果左为空右不为空说明p，q节点都在右
        if (left == nullptr && right != nullptr) {
            return right;
        // 如果左不为空右为空说明p，q节点都在左
        } else if (right == nullptr && left != nullptr) {
            return left;
        // 如果左为空右为空说明p，q节点不存在
        } else if (right == nullptr && left == nullptr) {
            return nullptr;
        }
        // 如果左不为空右不为空说明p，q节点各自存在左右子树
        return root;
    }
};